package leetcode.programmer;

public class FloodFill {

    int[] dx = {-1, 0, 0, 1};
    int[] dy = {0, 1, -1, 0};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        boolean[][] used = new boolean[image.length][image[0].length];
        dfs(image, sr, sc, newColor, image[sr][sc], used);
        return image;
    }

    private void dfs(int[][] image, int x, int y, int newColor, int start, boolean[][] used) {
        if (x < 0 || x >= image.length || y < 0 || y >= image[0].length || image[x][y] != start || used[x][y]) {
            return;
        }
        used[x][y] = true;
        image[x][y] = newColor;
        for (int i = 0; i < 4; i++) {
            int mx = dx[i] + x;
            int my = dy[i] + y;
            dfs(image, mx, my, newColor, start, used);
        }
    }

}
